package pl.pw.gis.gc_sa.algo;

import java.util.HashMap;
import java.util.Map;

import pl.pw.gis.gc_sa.data.Graph;
import pl.pw.gis.gc_sa.data.Vertex;
import pl.pw.gis.gc_sa.data.VertexChange;
import pl.pw.gis.gc_sa.utils.Utils;

/**
 * Klasa dziedziczaca po Cost wykorzystywana do obliczania koszty biezacego
 * kolorowania na podstawie funkcji kosztu z artykulu (Johnson, D. S., i inni.
 * Optimization by Simulated Annealing: An Experimental Evaluation; Part II,
 * Graph Coloring and Number Partitioning. Operations Research. May-June, 1991,
 * Tom 39.) Wykorzystuje informacje o liczbie kolorow i konfliktow dla kazdego z
 * nich w poprzednim rozwiazaniu, by szybciej obliczac biezacy koszt
 * 
 * @author Lukasz
 * 
 */
public class CostFromArticle extends Cost {
    private Map<Integer, Integer> mColorsCountMap;
    private Map<Integer, Integer> mConflictsMap;

    private int mOldColorVertexConflictsCount;
    private int mNewColorVertexConflictsCount;

    /**
     * Konstruktor klasy
     * 
     * @param graph
     *            graf dla ktorego liczone beda koszty
     * @param initialSol
     *            biezace rozwiazanie
     */
    public CostFromArticle(Graph graph, int[] initialSol) {
        super(graph, initialSol);
        mColorsCountMap = getColorsMap(mSolution);
        mConflictsMap = getConflictsMap(mGraph, mSolution);
        mCost = Utils.naiveArticleCostFunction(mSolution, mGraph);
    }

    /**
     * Zwraca koszt kolorowania, po wprowadzenie zadanej zmiany
     * 
     * @param vc
     *            obiekt opisujacy zmiane
     * 
     * @return wyliczony koszt po zmianie
     */
    @Override
    public int costAfterChange(VertexChange vc) {
        int colorsCostChange = getColorsCostChange(vc);
        int conflictsCostChange = getConflictsCostChange(vc);

        return mCost + colorsCostChange + conflictsCostChange;
    }

    /**
     * Metoda odswieza pola klasy na podstawie wprowadzonych zmian oraz
     * aktualizuje biezaca wartosc kosztu
     * 
     * @param vc
     *            obiekt zawierajacy informacje o zmianach
     * @param newCost
     *            nowa biezaca wartosc kosztu
     */
    @Override
    public void applyChange(VertexChange vc, int newCost) {
        mCost = newCost;
        updateClassData(vc);
    }

    /**
     * Metoda liczaca zmiane wartosci czesci funkcji kosztu, zalezna od
     * licznosci kazdej z klas kolorow. Idea polega na tym, aby pod uwage brac
     * tylko nowa i stara klase koloru zmienianego wierzcholka, jako ze tylko
     * dla nich zmienia sie ich licznosc
     * 
     * @param vc
     *            obiekt opisujacy biezaca zmiane
     * @return wartosc zmiany
     */
    private int getColorsCostChange(VertexChange vc) {
        int oldOriginalClassCost = 0;
        int newOriginalClassCost = 0;
        int oldChangedClassCost = 0;
        int newChangedClassCost = 0;

        oldOriginalClassCost = -sqPow(mColorsCountMap.get(vc.getOldColor()));
        newOriginalClassCost = -sqPow(mColorsCountMap.get(vc.getOldColor()) - 1);
        if (mColorsCountMap.get(vc.getNewColor()) != null) {
            oldChangedClassCost = -sqPow(mColorsCountMap.get(vc.getNewColor()));
            newChangedClassCost = -sqPow(mColorsCountMap.get(vc.getNewColor()) + 1);
        } else {
            oldChangedClassCost = 0;
            newChangedClassCost = -1;
        }

        int colorCostChange = newOriginalClassCost - oldOriginalClassCost
                + newChangedClassCost - oldChangedClassCost;

        return colorCostChange;
    }

    /**
     * Metoda liczaca zmiane wartosci czesci funkcji kosztu, zalezna od liczby
     * konfliktow w kazdej z klas. Idea polega na tym, aby pod uwage brac
     * wylacznie liczbe konfliktow w stare oraz nowej klasie kolorowanego
     * wierzcholka, jako ze tylko ich dotyczy zmiana koloru wierzcholka
     * 
     * @param vc
     *            obiekt opisujacy biezaca zmiane
     * @return wartosc zmiany
     */
    private int getConflictsCostChange(VertexChange vc) {
        int oldOriginalClassCost = 0;
        int newOriginalClassCost = 0;
        int oldChangedClassCost = 0;
        int newChangedClassCost = 0;
        mOldColorVertexConflictsCount = 0;
        mNewColorVertexConflictsCount = 0;
        Vertex v = mGraph.getVertices().get(vc.getVertexId());

        oldOriginalClassCost = mColorsCountMap.get(vc.getOldColor())
                * mConflictsMap.get(vc.getOldColor());
        if (oldOriginalClassCost != 0) {
            for (Vertex n : v.getAdjacent()) {
                if (mSolution[n.getId()] == vc.getOldColor())
                    mOldColorVertexConflictsCount++;
            }
            newOriginalClassCost = (mColorsCountMap.get(vc.getOldColor()) - 1)
                    * (mConflictsMap.get(vc.getOldColor()) - mOldColorVertexConflictsCount);
        }

        if (mColorsCountMap.containsKey(vc.getNewColor())) {
            oldChangedClassCost = mColorsCountMap.get(vc.getNewColor())
                    * mConflictsMap.get(vc.getNewColor());

            for (Vertex n : v.getAdjacent()) {
                if (mSolution[n.getId()] == vc.getNewColor())
                    mNewColorVertexConflictsCount++;
            }
            newChangedClassCost = (mColorsCountMap.get(vc.getNewColor()) + 1)
                    * (mConflictsMap.get(vc.getNewColor()) + mNewColorVertexConflictsCount);
        }

        int conflictsCostChange = newOriginalClassCost - oldOriginalClassCost
                + newChangedClassCost - oldChangedClassCost;

        return conflictsCostChange * 2;
    }

    /**
     * Metoda odswiezajaca pola klasy na podstawie zmian opisanych w vc
     * 
     * @param vc
     *            obiekt opisujacy biezace zmiany
     */
    private void updateClassData(VertexChange vc) {
        if (!mColorsCountMap.containsKey(vc.getNewColor())) {
            mColorsCountMap.put(vc.getNewColor(), 1);
        } else {
            mColorsCountMap.put(vc.getNewColor(),
                    mColorsCountMap.get(vc.getNewColor()) + 1);
        }
        mColorsCountMap.put(vc.getOldColor(),
                mColorsCountMap.get(vc.getOldColor()) - 1);

        mConflictsMap.put(vc.getOldColor(), mConflictsMap.get(vc.getOldColor())
                - mOldColorVertexConflictsCount);
        if (mConflictsMap.containsKey(vc.getNewColor())) {
            mConflictsMap.put(vc.getNewColor(),
                    mConflictsMap.get(vc.getNewColor())
                            + mNewColorVertexConflictsCount);
        } else {
            mConflictsMap.put(vc.getNewColor(), mNewColorVertexConflictsCount);
        }

        mSolution[vc.getVertexId()] = vc.getNewColor();
    }

    /**
     * Metoda tworzy mape konfliktow kolorow, gdzie dla kazdego istniejacego
     * koloru w zadanej tablicy, liczona jest liczba konfliktow (zlych krawedzi)
     * - czyli sytuacji, gdzie wierzcholki polaczone dana krawedzia maja ten sam
     * kolor
     * 
     * @param graph
     *            graf zawierajacy informacje o polaczeniach miedzy
     *            wierzcholkami
     * @param colors
     *            tablicza zawierajaca kolory wierzcholkow grafu
     * @return mape konfliktow kolorow, gdzie dla kazdego koloru z tablicy
     *         wpisana jest liczba konfliktow <0,n-1>
     */
    protected static Map<Integer, Integer> getConflictsMap(Graph graph,
            int[] colors) {
        Map<Integer, Integer> conflicts = new HashMap<Integer, Integer>();

        for (int i = 0; i < colors.length; i++)
            conflicts.put(colors[i], 0);

        for (Vertex v : graph.getVertices()) {
            for (Vertex n : v.getAdjacent()) {
                if (n.getId() > v.getId()) {
                    if (colors[n.getId()] == colors[v.getId()]) {
                        int color = colors[v.getId()];

                        Integer prevVal = conflicts.get(color);
                        conflicts.put(color, prevVal + 1);
                    }
                }
            }
        }

        return conflicts;
    }

    /**
     * Zwraca mape zliczajaca ilosc obiektow wszystkich klas
     * 
     * @param colorsArray
     *            tablica przypisanych kolorow
     * @return haszmapa z licznoscia klas
     */
    public static Map<Integer, Integer> getColorsMap(int[] colorsArray) {
        Map<Integer, Integer> colorsMap = new HashMap<Integer, Integer>();
        for (int color : colorsArray) {
            if (!colorsMap.containsKey(color))
                colorsMap.put(color, 1);
            else {
                Integer prevVal = colorsMap.get(color);
                colorsMap.put(color, prevVal + 1);
            }
        }
        return colorsMap;
    }

    /**
     * Metoda zwracajaca zapisana wartosc kosztu
     * 
     * @return zapisana wartosc kosztu
     */
    public int getCurrentCost() {
        return mCost;
    }

    /**
     * Podreczna metoda do obliczania kwadratu wartosci
     * 
     * @param val
     *            zadana wartosc
     * @return kwadrat zadanej wartosci
     */
    private int sqPow(int val) {
        return val * val;
    }
}
